[洛谷P1967][NOIP2013]货车运输

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

第一行有两个用一个空格隔开的整数n,m表示A国有n座城市和m条道路。

接下来m行每行3个整数 x, y, z每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x不等于y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

输出格式：

共有q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出−1。

输入输出样例

输入样例1：

1
2
3
4
5
6
7
8
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

输出样例1：

1
2
3
3
-1
3

说明

对于 30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,000；

对于 60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,000；

对于 100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,000

题解

部分内容摘自2013年鉴

其实这道题就是比较简单的图论题（作为最后一天的最后一题来讲）
首先对图做最大生成树（方法和最小生成树一样），得到的是一个森林。对于每一辆车，设其起点、终点分别为x,y，如果x,y连通，那么x,y在一棵树上，该火车最多能运送的货物为x,y之间的路径中的最小的边c。因为如果在原图中存在一条路径连接x,y,且所有的边的边权都大于c，那么最大生成树一定求错了（因为将该路径上的边加到生成树中去，必然形成包括c边在内的一个环，此时删除c边可以得到更大的生成树）
所以此题变成了求各个点对在树种路径上的最小边。

方法一：暴力

就是去实现上面的步骤，求LCA的时候暴力来求，不用倍增，可以AC（具体见暴力），如果是一条链的话会被卡，然而并没有这种数据。

方法二：倍增

此时我们可以用倍增的子项求某两个点的路径上的最小边。首先纪录每个点向上（向树根）走$v(v=2^0,2^1,\dots)$步所经过的路径中最小边是多少。对于一个询问x,y，可以求出其最近公共祖先z，然后求x，z之间的最小边和y，z之间的最小边。
时间复杂度为$O(mlogm+n+logn)$

方法三：

标称用的方法并不是倍增法，只需要在最大生成树的里面加一个求解的询问就行。首先用一个数组ans表示最终的答案，ans[i]表示第i个询问最多能运的货物数量。再用kruskal算法中，每将一条边加到最大生成树里面，那么这条边会将连个点集合并到一起。
如果某个询问i，他的两个点x，y分别属于这两个点集，那么这个询问的答案就是新加入的这条边的边权（因为此时x,y已经在一棵树中，所以x,y之间有路径。由于Kruskal求最大生成树时是由边权从大到小加入的，所以当前边是路径上边权最小的边）我们只需要在每个电商挂一个询问的链，每次询问时将两个询问的链合并到一起，合并的时候选取询问较少的那个链进行扫描并更新答案。所以对链的操作的时间复杂度为[合并次数+每次合并时扫描的询问个数和]。时间的小号主要在扫描，但是我们可以发现，每次扫描都只扫描了较少的那一部分，设长度为L，并且合并后询问的长度增长到2L以上。所以总的时间复杂度为$O(mlogm+qlogq)$

代码

LCA暴力，代码来自本校神犇yanyu

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=11000;
const int maxm=51000;
int head[maxn],Next[maxm<<1],ver[maxm<<1],weigh[maxm<<1];
int f[maxn],fa[maxn],dis[maxn],deep[maxn];
int n,m,q,tot;
struct node{
    int x,y,weigh;
}edge[maxm<<1];
 
inline void add(int x,int y,int w){
    ver[++tot]=y;weigh[tot]=w;Next[tot]=head[x];head[x]=tot;
}
 
bool cmp(node a,node b){
    return a.weigh > b.weigh;    
}
 
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
 
void dfs(int x){
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(deep[y]==0){
            dis[y]=weigh[i];
            deep[y]=deep[x]+1;
            f[y]=x;
            dfs(y);
        }
    }
}
 
int lca(int x,int y){
    int ans=1<<30;
    if(deep[x]>deep[y]) swap(x,y);
    while(deep[x]!=deep[y]){
        ans=min(ans,dis[y]);
        y=f[y];
    }
    while(x!=y){
        ans=min(ans,min(dis[x],dis[y]));
        x=f[x],y=f[y];
    }
    return ans;
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].weigh);
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=m;i++){
        int fx=find(edge[i].x);
        int fy=find(edge[i].y);
        if(fx!=fy){
            fa[fx]=fy;
            add(edge[i].x,edge[i].y,edge[i].weigh);
            add(edge[i].y,edge[i].x,edge[i].weigh);
        }
    }
    for(int i=1;i<=n;i++)
        if(deep[i]==0) dfs(i);
    scanf("%d",&q);
    for(int i=1,x,y;i<=q;i++){
        scanf("%d%d",&x,&y);
        if(find(x)!=find(y)) printf("-1\n");
        else printf("%d\n",lca(x,y));
    }
    return 0;
}

倍增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN =50005;
int dep[MAXN];
int n,m;
struct node{
    int x,y,w;
}edge[MAXN];
int fa[MAXN];
int Nt[MAXN],Head[MAXN],wight[MAXN],to[MAXN],tot;
int f[20005][21],w[20005][21];

void add(int x,int y,int v){
    Nt[++tot]=Head[x];
    to[tot]=y;
    wight[tot]=v;
    Head[x]=tot;
}

int Find(int x){
    if(fa[x]!=x)fa[x]=Find(fa[x]);
    return fa[x]; 
}

bool cmp(node a,node b){
    return a.w>b.w;
}

void dfs(int x){
    for(int i=Head[x];i;i=Nt[i]){
        int y=to[i];
        if(dep[y])continue;
        dep[y]=dep[x]+1;
        f[y][0]=x;
        w[y][0]=wight[i];
        dfs(y);
    }
}

void kruskal(){
    sort(edge+1,edge+m+1,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int fa_x=Find(edge[i].x),fa_y=Find(edge[i].y);
        if(fa_x==fa_y)continue;
        fa[fa_x]=fa_y;
        add(edge[i].x,edge[i].y,edge[i].w);
        add(edge[i].y,edge[i].x,edge[i].w);
    }
}

int lca(int x,int y){
    if(Find(x)!=Find(y)) return -1;
    int ans=1<<30;
    if(dep[x]>dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[y][i]]>=dep[x]){
            ans=min(ans,w[y][i]);
            y=f[y][i];
        }
    }
    if(x==y)return ans;
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            ans=min(ans,min(w[x][i],w[y][i]));
            y=f[y][i];
            x=f[x][i];
        }
    }
    ans=min(ans, min(w[x][0], w[y][0]));
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
    }
    kruskal();
    int q;
    cin>>q;
    for(int i=1;i<=n;i++){
        if(!dep[i]){
            dep[i]=1;
            dfs(i);
            f[i][0]=i;
            w[i][0]=1<<30;
        }
    }
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
            w[j][i]=min(w[j][i-1],w[f[j][i-1]][i-1]);
        }
    }
    for(int i=1;i<=q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}